/**
 * 给定<Wi,Li>的数组，当选取第i个元素时，
 * 意味着能收获Wi，且接下来Li个元素均不能取。问最大可能的收获
 * 
 * 注意到设Di是到i为止的最大收获，则Di由之前的哪些Dj决定是不好确定的
 * 除非做一个预处理
 * 
 * 可以使用刷表法，但是要改一下规划模板
 * 令Di是[1...i-1]的最大收获
 * 
 * 则在位置i时，选i可以影响D[i+Li+1]，这里要注意边界处理
 * 不选i可以影响D[i+1]
 *
 */

class Solution {

using llt = long long;
using vi = vector<int>;

int N;
vector<llt> D;

public:
    long long mostPoints(vector<vector<int>>& questions) {
        N = questions.size();
        D.assign(N + 2, 0);
        questions.insert(questions.begin(), {0, 0});
        for(int i=1;i<=N;++i){
            auto wi = questions[i][0];
            auto skip = questions[i][1];
            // 不选就能影响到D[i+1];
            chkmax(D[i + 1], D[i]);
            // 选就能影响到D[i+skip+1]
            auto p = i + skip + 1;
            if(p > N + 1) p = N + 1;
            chkmax(D[p], D[i] + wi);
        }
        return D[N + 1];
    }
    void chkmax(llt & d, llt a){
        if(d < a) d = a;
    }
};